# coding:utf-8

class SingleNode(object):
    '''
    单节点:
    两部分:一部分保存当前节点的数据,另一部分保存下一个节点的地址
    '''

    def __init__(self, item):
        self.item = item
        self.next = None


class SingleLinkList(object):
    '''单链表'''

    def __init__(self, node):
        self.__head = self.__get_node(node)

    def __get_node(self, item):
        if item is None:
            return None
        elif isinstance(item, SingleNode):
            return item
        else:
            return SingleNode(item)

    def is_empty(self):
        '''链表是否为空'''
        return self.__head is None

    def length(self):
        '''链表长度'''
        current = self.__head
        count = 0
        while current:
            count += 1
            current = current.next
        return count

    def travel(self):
        '''遍历链表'''
        current = self.__head
        while current:
            print(current.item)
            current = current.next

    def add(self, item):
        '''头部添加'''
        node = self.__get_node(item)
        node.next = self.__head
        self.__head = node

    def append(self, item):
        '''尾部加'''
        node = self.__get_node(item)
        current = self.__head
        if self.is_empty():
            self.__head = node
        else:
            while current.next:
                current = current.next
            current.next = node

    def insert(self, pos, item):
        '''指定位置加'''
        if pos > self.length():
            self.append(item)
        elif pos <= 0:
            self.add(item)
        else:
            node = self.__get_node(item)
            prenode = self.__head
            count = 0
            stop = pos - 1
            while count < stop:
                count += 1
                prenode = prenode.next
            node.next = prenode.next
            prenode.next = node

    def remove(self, item):
        '''移除元素'''
        current = self.__head
        pre = None
        while current:
            if current.item == item:
                if current == self.__head:  # 第一个
                    self.__head = current.next
                else:
                    pre.next = current.next
                break
            else:
                pre = current
                current = current.next

    def search(self, item):
        '''查找元素是否存在'''
        current = self.__head
        while current:
            if current.item == item:
                return True
            else:
                current = current.next
        return False


if __name__ == '__main__':
    ll = SingleLinkList()
    # print(ll.is_empty())
    # print(ll.length())
    # ll.append(1000)
    # print(ll.is_empty())
    # print(ll.length())
    ll.append(1)
    ll.add(132)
    ll.insert(0, 100)
    ll.insert(12, 12)
    ll.insert(2, 2)
    ll.insert(2, 3)
    ll.travel()
    # print(ll.search(222))
    ll.remove(2)
    ll.travel()
# 100 132 2 1 12
